The concept of transaction has been widely used in the database field. Differing from the conventional transaction concept, transaction in this disclosure is a special concept in parallel computing field, and refers to the execution of multiple operations, such that the multiple operations appear to be executed together automatically without any intervening operation. For example, if a memory address is accessed within a transaction, the memory address should not be modified by other codes outside the transaction until the transaction completes.
Transaction can be implemented directly at computer architecture level. The hardware system implementing transaction at architecture-level is called system enabling Transaction Memory (TM). Using system enabling Transactional Memory can improve software productivity because programmers may not need to worry about using conventional “lock” mechanism to protect shared data, while keeping the performance in an acceptable scope.
One method for implementing a system enabling Transactional Memory is introduced as follows. A dedicated buffer is added into a processor chip. Instead of being written into memory directly, data modified by a transaction (speculative data) is stored in the dedicated buffer. If two transactions access the same memory address and at least one of them performs a write operation, one of these two transactions has to rollback and re-execute, while the other one continues. This situation is called conflict. If there is no conflict, the data temporarily stored in the dedicated buffer is written into memory at the end of the transaction. This action is called commit. That is, a transaction is executed speculatively, and its result is committed to the memory only if all operations in the transaction are successfully executed speculatively.
FIG. 1 schematically illustrates the principle of such a system enabling Transactional Memory. As illustrated in FIG. 1, hardware buffers 1012 or 1022 are provided in a system enabling transactional memory, for temporarily storing all data to be written by a transaction, i.e., speculative data, during the execution of the transaction. The speculative data stored in the hardware buffers is committed to a memory via a bus 1030 only after the successful execution of all program codes in the transaction. It should be noted that, as another implementation method, hardware buffer 1012 and data cache 1014 may be implemented in one physical hardware device, while hardware buffer 1022 and data cache 1024 may be implemented in one physical hardware device including at least one processor 1010, 1020. With respect to the present invention, this implementation method is substantially the same as that illustrated in FIG. 1, and the spirit of the present invention is applicable to this implementation method also.
In the prior art, all transactions are executed speculatively. During the speculative execution of a transaction, all data written by the transaction is temporarily stored in a hardware buffer, and only if all program codes in the transaction have been executed (in speculation) successfully, the speculative data stored in the hardware buffer is committed to a memory. At that time, the transaction is accomplished successfully.
However, the hardware buffer cannot be very large. If a transaction is large (accesses a lot of addresses), the buffer cannot hold all of the data. Therefore, the buffer will overflow. In the prior art, buffer overflow forces the transaction to abort (referred to as transaction overflow hereinafter) and then the transaction has to be re-executed. In general, when a transaction is re-executed, a time-consuming method is adopted, in order to prevent another overflow, for example by resorting back to traditional lock-based method to run. This invention does not focus on any specific method for handling overflow. In the following description, lock-based method is adopted as an example for the purpose of illustration, and it generally refers to any time-consuming method for handling overflow.
As described above, there are two methods to run a transaction. If the transaction is small, it is executed by a fast method in which the speculative data is stored in a hardware buffer (i.e., execution by using hardware buffer). On the other hand, if the transaction is large, it is run by the slow method based on locking.
In the prior art, however, before the execution of a transaction, it cannot be known whether the transaction will overflow, that is, it cannot be known whether the hardware buffer will overflow during the execution of the transaction. Hence, for any transaction, it is assumed that it will not overflow at the beginning and it is executed by using a hardware buffer. The execution of a large transaction will be aborted due to buffer overflow, and the overflowed transaction is re-executed by the second slow method. Therefore, a large transaction has to be tentatively executed for the first time, and then be re-executed by the lock-based method after its abort. In such a scenario, the first-time execution of a large transaction (i.e., the aborted execution) wastes time and energy, and occupies system resources.
The U.S. patent application document US2005/0060559A discloses a method for determining whether a transaction will overflow or not by running a pseudo-transaction. However, in such method, one execution of the transaction is also necessary to determine whether an overflow will occur or not, and therefore it also wastes time and energy, and occupies system resources.
A hybrid hardware and software implementation of a transactional memory system is disclosed in the U.S. Patent application document US2006/0085591, in which if the hardware transactional memory system overflows, it switches to a software transactional memory system to be executed once again. That is, that patent document provides a method for handling overflowed transaction at the cost of one execution of the transaction with overflow.